home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 2010 April / PCWorld0410.iso / pluginy Firefox / 13316 / 13316.xpi / content / treeArranger.js < prev    next >
Encoding:
JavaScript  |  2009-07-25  |  18.2 KB  |  619 lines

  1.  
  2. /* Copyright (C) 2009 Norman Solomon
  3.  * e-mail: historytree.addon@yahoo.com
  4.  * 
  5.  * The contents of this file are subject to the Mozilla Public License Version
  6.  * 1.1 (the "License"); you may not use this file except in compliance with
  7.  * the License. You may obtain a copy of the License at http://www.mozilla.org/MPL/
  8.  *
  9.  * Software distributed under the License is distributed on an "AS IS" basis,
  10.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  11.  * for the specific language governing rights and limitations under the License.
  12.  */
  13.  
  14. // ******************************************************************************************
  15. // *****                                                                                *****
  16. // *****    This JS file implements Sven Moen's algorithm to arrange a tree for tidy    *****
  17. // *****    drawing. Sven's algorithm ALWAYS lays out the tree horizontally, but it     *****
  18. // *****    has been adjusted here (with functions added) to layout a vertical tree     *****
  19. // *****  --------------------------------------------------------------------------    *****
  20. // *****                                                                                *****
  21. // *****   FIRST THE CLASSES - Passed properties MUST be set when a class is created    *****
  22. // *****    Java variable type declarations are shown in a comment above each class     *****
  23. // *****                                                                                *****
  24. // ******************************************************************************************
  25.  
  26. // ---------------------------------------------------------------
  27. // TreeNode objects are stored in the global gTreeNodes[] Array
  28. // (TreeNode p, TreeNode c, TreeNode s, int w, int h)
  29. // ---------------------------------------------------------------
  30. var TreeNode = function (p, c, s, w, h)
  31. {
  32.     // ----------------------------------------------------------
  33.     // Props needed for ANY implementation of Sven's algorithm
  34.     // ----------------------------------------------------------
  35.     this.parent = p;
  36.     this.child = c;
  37.     this.sibling = s;
  38.     
  39.     // Properties that determine node size and overall tree size
  40.     this.width = w;
  41.     this.height = h;
  42.     this.border = 0;
  43.  
  44.     // Properties calculated in Sven's tArrLayout() method
  45.     this.pos = new Point(0, 0);
  46.     this.offset = new Point(0, 0);
  47.     this.contour = new Polygon();
  48.  
  49.     // -------------------------------------------------------
  50.     // Properties specific to this FF extension application
  51.     // -------------------------------------------------------
  52.     this.histNode = null;        // Ref to this TreeNodes's associated HistoryNode
  53.     this.isOpenPage = false;    // Set = true if underlying web-page is open in FF
  54.  
  55.     this.inOpenTab = null;        // Set = true if Tab root TreeNode is open in FF
  56.     this.tabTreeSize = 0;        // Number of TreeNode's in a Tab sub-tree
  57.  
  58.     this.childCopy = null;        // Used to expand/contract sub-trees
  59.     this.hiddenTreeSize = 0;    // Size of hidden sub-tree below node
  60.     this.hidden = false;        // Set = true if this TreeNode is in hidden sub-tree
  61.  
  62.     // Props used to restore tree's overall state to its initial state
  63.     this.parentBak = null;
  64.     this.childBak = null;
  65.     this.siblingBak = null;
  66.  
  67.     // Props for detection of mouse-click on TreeView node
  68.     this.hidBtnWid = 0;
  69.     this.btnPanelWid = 0;
  70.     this.btnPanelX = 0;
  71.  
  72.     // Props for GridView image drawing and mouse-click detection
  73.     this.gridViewImgX = 0;
  74.     this.gridViewImgY = 0;
  75.     this.gridViewImgWid = 0;
  76.     this.gridViewTabNum = 0;
  77.     
  78.     // Description strings for text displayed inside this TreeNode
  79.     this.histNodeDesc = "";        // Used to check whether descLine's are up to date
  80.     this.descLine1 = "";        // Set in function setDescriptionLinesFor()
  81.     this.descLine2 = "";        // Set in function setDescriptionLinesFor()
  82. }
  83.  
  84. // -----------------------------------------------------------------------
  85. // Polylines are used to build the sub-tree contours around each TreeNode
  86. // (int dx, int dy, PolyLine link)
  87. // -----------------------------------------------------------------------
  88. var PolyLine = function (dx, dy, link)
  89. {
  90.     this.dx = dx;
  91.     this.dy = dy;
  92.     this.link = link;
  93. }
  94.  
  95. // -----------------------------------------------------------------------
  96. // Represents a polygon area for use in spacing/positioning calculations
  97. // *** No props are passed to the class instantiator when object created
  98. // -----------------------------------------------------------------------
  99. var Polygon = function ()
  100. {
  101.     // Four Polyline objects
  102.     this.lower_head;
  103.     this.lower_tail;
  104.     this.upper_head;
  105.     this.upper_tail;
  106. }
  107.  
  108. // -----------------------------------------------------------------------
  109. // JS equivalent of Java Point object (used by several functions below)
  110. // (int x, int y)
  111. // -----------------------------------------------------------------------
  112. var Point = function (x, y)
  113. {
  114.    this.x = x;
  115.    this.y = y;
  116. }
  117.  
  118. // ******************************************************
  119. // *****                                            *****
  120. // *****       FUNCTIONS WRITTEN BY Sven Moen       *****
  121. // *****   --------------------------------------   *****
  122. // *****    Java variable type declarations are     *****
  123. // *****    shown in a comment above each method    *****
  124. // *****                                            *****
  125. // ******************************************************
  126.  
  127. // -----------------------------------------------------------
  128. // Lays out the tree node spacing by setting Node offsets
  129. // (TreeNode t)
  130. // -----------------------------------------------------------
  131. function tArrLayout(t)
  132. {
  133.     var c; // TreeNode
  134.     
  135.     // ------------------------------------
  136.     // Exit if the passed node is null
  137.     if (t === null)
  138.         return;
  139.  
  140.     // ***********************************
  141.     // *******   RECURSIVE LOOP   ********
  142.     // ***********************************
  143.     c = t.child;
  144.     while (c != null)
  145.     {
  146.         tArrLayout(c);
  147.         c = c.sibling;
  148.     }
  149.     
  150.     // ------------------------------------
  151.     // Set contour property of this node
  152.     if (t.child !== null)
  153.         // Create the contour around sub-tree below 
  154.         tArrAttachParent(t, tArrJoin(t));
  155.     else
  156.         // Create the contour round ONLY this leaf
  157.         tArrLayoutLeaf(t);
  158. }
  159.  
  160. // -----------------------------------------------------------
  161. // Attaches specified node to its children, setting offsets
  162. // (TreeNode t, int h)
  163. // -----------------------------------------------------------
  164. function tArrAttachParent(t, h)
  165. {
  166.     var x, y1, y2;
  167.  
  168.     x = t.border + LEVEL_SPACE;
  169.     y2 = (h - t.height) / 2 - t.border;
  170.     y1 = y2 + t.height + (2 * t.border) - h;
  171.     
  172.     t.child.offset.x = x + t.width;
  173.     t.child.offset.y = y1;
  174.     
  175.     // Set contour property of the passed node
  176.     t.contour.upper_head = new PolyLine(t.width, 0, new PolyLine(x, y1, t.contour.upper_head));
  177.     t.contour.lower_head = new PolyLine(t.width, 0, new PolyLine(x, y2, t.contour.lower_head));
  178. }
  179.  
  180. // -----------------------------------------------------------
  181. // Sets passed nodes contour property using Polyline objects
  182. // (TreeNode t)
  183. // -----------------------------------------------------------
  184. function tArrLayoutLeaf(t)
  185. {
  186.     // Draw a contour around leaf node & store it in the nodes contour property
  187.     t.contour.upper_tail = new PolyLine(t.width + (2 * t.border), 0, null);
  188.     t.contour.upper_head = t.contour.upper_tail;
  189.     t.contour.lower_tail = new PolyLine(0, - t.height - (2 * t.border), null);
  190.     t.contour.lower_head = new PolyLine(t.width + (2 * t.border), 0, t.contour.lower_tail);
  191.  
  192. // -----------------------------------------------------------
  193. // Merges t's children & returns height of resulting contour 
  194. // (TreeNode t)
  195. // -----------------------------------------------------------
  196. function tArrJoin(t)
  197. {
  198.     // *** NOTE - t is parent and c are it's children
  199.     var c;            // TreeNode
  200.     var d, h, sum;  // integers
  201.     
  202.     // --------------------------------------------
  203.     // Set parent contour equal to child contour
  204.     c = t.child;
  205.     t.contour = c.contour;
  206.  
  207.     // --------------------------------------------
  208.     // Initialize values used in loop
  209.     //sum = h = c.height + 2 * c.border;
  210.     h = c.height + (2 * c.border);
  211.     sum = h;
  212.  
  213.     // --------------------------------------------
  214.     // Loop round all children of parent t
  215.     c = c.sibling;
  216.     while(c != null)
  217.     {
  218.         d = tArrMerge(t.contour, c.contour);
  219.         c.offset.y = d + h;
  220.         c.offset.x = 0;
  221.         h = c.height + (2 * c.border);
  222.         sum += d + h;
  223.  
  224.         // Get next child
  225.         c = c.sibling;
  226.     }
  227.     // ---------------------------------
  228.     return sum;
  229. }
  230.  
  231. // -------------------------------------------------------------------
  232. // Merges two polygons and returns total height of resulting polygon 
  233. // (Polygon c1, Polygon c2)
  234. // -------------------------------------------------------------------
  235. function tArrMerge(c1, c2)
  236. {
  237.     // integers
  238.     var x = 0;
  239.     var y = 0;
  240.     var total = 0;
  241.     var d;
  242.  
  243.     // Polylines
  244.     var lower, upper, b;
  245.  
  246.     // --------------------------------------
  247.     upper = c1.lower_head;
  248.     lower = c2.upper_head;
  249.     
  250.     while(lower != null && upper != null)
  251.     {     
  252.         // compute tArrOffset total
  253.         d = tArrOffset(x, y, lower.dx, lower.dy, upper.dx, upper.dy);
  254.         y += d;
  255.         total += d;
  256.  
  257.         if (x + lower.dx <= upper.dx)
  258.         {
  259.             y += lower.dy;
  260.             x += lower.dx;
  261.             lower = lower.link;
  262.         }
  263.         else
  264.         {
  265.             y -= upper.dy;
  266.             x -= upper.dx;
  267.             upper = upper.link;
  268.         }
  269.     }
  270.  
  271.     // -------------------------------------------
  272.     // store result in c1 (calls tArrBridge function)
  273.     if (lower !== null)
  274.     {
  275.         b = tArrBridge(c1.upper_tail, 0, 0, lower, x, y);
  276.         c1.upper_tail = (b.link != null) ? c2.upper_tail : b;
  277.         c1.lower_tail = c2.lower_tail;
  278.     }
  279.     else // (upper)
  280.     {     
  281.         b = tArrBridge(c2.lower_tail, x, y, upper, 0, 0);
  282.         
  283.         if (b.link === null)
  284.             c1.lower_tail = b;
  285.     }
  286.  
  287.     c1.lower_head = c2.lower_head;    
  288.  
  289.     // -----------------------------------
  290.     // Return the total
  291.     return total;
  292. }
  293.  
  294. // ------------------------------------------------------------------
  295. // Returns a value used to set contour - Only called from tArrMerge()
  296. // (PolyLine line1, int x1, int y1, PolyLine line2, int x2, int y2)
  297. // ------------------------------------------------------------------
  298. function tArrBridge(line1, x1, y1, line2, x2, y2)
  299. {
  300.     var dy, dx, s;  // integers
  301.     var r;            // Polyline
  302.  
  303.     dx = x2 + line2.dx - x1;
  304.     
  305.     if (line2.dx === 0)
  306.     {
  307.         dy = line2.dy;
  308.     }
  309.     else
  310.     {
  311.         s = dx * line2.dy;
  312.         dy = s / line2.dx;
  313.     }
  314.  
  315.     r = new PolyLine(dx, dy, line2.link);
  316.     line1.link = new PolyLine(0, y2 + line2.dy - dy - y1, r);
  317.  
  318.     return r;
  319.  
  320. // ---------------------------------------------------------
  321. // Calculates the tArrOffset for specified points
  322. // (int p1, int p2, int a1, int a2, int b1, int b2)
  323. // ---------------------------------------------------------
  324. function tArrOffset(p1, p2, a1, a2, b1, b2) 
  325. {
  326.     var d, s, t;  // integers
  327.  
  328.     if (b1 <= p1 || p1 + a1 <= 0)
  329.         return 0;
  330.     
  331.     t = b1 * a2 - a1 * b2;
  332.     // ----------------------
  333.     if (t > 0)
  334.     // ----------------------
  335.     {
  336.         if (p1 < 0)
  337.         {
  338.             s = p1 * a2;
  339.             d = s / a1 - p2;
  340.         }
  341.         else if (p1 > 0)
  342.         {
  343.             s = p1 * b2;
  344.             d = s / b1 - p2;
  345.         }
  346.         else
  347.         {
  348.             d = -p2;
  349.         }
  350.     }
  351.     // ----------------------
  352.     else if (b1 < p1 + a1)
  353.     // ----------------------
  354.     {
  355.         s = (b1 - p1) * a2;
  356.         d = b2 - (p2 + s / a1);
  357.     }
  358.     // ----------------------
  359.     else if (b1 > p1 + a1)
  360.     // ----------------------
  361.     {
  362.         s = (a1 + p1) * b2;
  363.         d = s / b1 - (p2 + a2);
  364.     }
  365.     // ----------------------
  366.     else
  367.     // ----------------------
  368.     {
  369.         d = b2 - (p2 + a2);
  370.     }
  371.     
  372.     // ======================
  373.     if (d > 0)
  374.         return d;
  375.     else
  376.         return 0;
  377. }
  378.  
  379. // -----------------------------------------------------------------
  380. // Calculates pos.x and pos.y for all nodes by traversing the tree 
  381. // and using the nodes offset.x and offset.y values
  382. // (TreeNode t, int off_x, int off_y)
  383. // -----------------------------------------------------------------
  384. function tArrPlantTree(t, off_x, off_y)
  385. {
  386.     var c, s;    // TreeNodes
  387.     var cur_y;  // integer
  388.     
  389.     // --------------------------------
  390.     // Set node screen (x,y) position
  391.     t.pos.x = off_x + t.offset.x;
  392.     t.pos.y = off_y + t.offset.y;
  393.  
  394.     // --------------------------------
  395.     // Set global for whole tree
  396.     if (t.pos.y < gTreeMinY)
  397.         gTreeMinY = t.pos.y;
  398.  
  399.     // --------------------------------
  400.     // Plant child node 
  401.     c = t.child;
  402.     if(c !== null)
  403.     {
  404.         // ***********************************
  405.         // *******   RECURSIVE CALL   ********
  406.         // ***********************************
  407.         tArrPlantTree(c, t.pos.x, t.pos.y);
  408.  
  409.         // Plant sibling nodes 
  410.         s = c.sibling;
  411.         cur_y = t.pos.y + c.offset.y;
  412.         
  413.         while(s != null)
  414.         {
  415.             // ***********************************
  416.             // *******   RECURSIVE CALL   ********
  417.             // ***********************************
  418.             tArrPlantTree(s, t.pos.x + c.offset.x, cur_y);
  419.             cur_y += s.offset.y;
  420.             s = s.sibling;
  421.         }
  422.     }
  423. }
  424.  
  425.  
  426. // ********************************************************************************
  427. // *****                                                                      *****
  428. // *****    PROCEDURES ADDED TO Sven Moen's algorithm TO ALLOW VERTICAL          *****
  429. // *****    TREES TO BE LAID OUT TIDILY - INCLUDING SOME USEFUL UTILITY       *****
  430. // *****    FUNCTIONS FOR ANY IMPLEMENTATION OF THE Sven Moen algorithm          *****
  431. // *****  ------------------------------------------------------------------  *****
  432. // *****   Java type declarations are shown in a comment above each method    *****
  433. // *****                                                                      *****
  434. // ********************************************************************************
  435.  
  436. // ----------------------------------------------------------------------------
  437. // 1) Adjusts horizontal tree position so it fits snugly in top left corner
  438. // 2) Changes tree to vertical orientation by swapping all TreeNode.(x,y)
  439. // *** NOTE - Sven Moen's algorithm ALWAYS lays out tree horizontally
  440. // (TreeNode root)
  441. // ----------------------------------------------------------------------------
  442. function changeTreeToVerticalLayout(root)
  443. {
  444.     // Initialize global variable
  445.     gTreeMinY = 0;    // integer
  446.  
  447.     // Private variables
  448.     var node;        // TreeNode
  449.     var tempX;        // integer
  450.     var yAddOn = 0;
  451.     if (root.child !== null)
  452.     {
  453.         node = root.child;
  454.         yAddOn = node.height - BOX_HEIGHT;
  455.     }
  456.  
  457.     // -----------------------------------------------
  458.     // *** NOTE - tArrPlantTree is a recursive procedure
  459.     tArrPlantTree(root, 0, 0);    
  460.     tArrPlantTree(root, 0, Math.abs(gTreeMinY));
  461.  
  462.     // Change tree to vertical orientation by swapping all TreeNode.(x,y)
  463.     for (var i = 0; i < gTreeNodes.length; i++)
  464.     {
  465.         // Get TreeNode from gTreeNodes[] and swap (x,y)
  466.         node = gTreeNodes[i];
  467.         if (!node.hidden)
  468.         {
  469.             // Swap x and y co-ordinates
  470.             tempX = node.pos.x;
  471.             node.pos.x = node.pos.y;
  472.             node.pos.y = tempX;
  473.             
  474.             // Adjust for taller Tab roots
  475.             if (node.height > BOX_HEIGHT)
  476.                 node.pos.x += Math.round(yAddOn / 2);
  477.             else if (node !== root)
  478.                 node.pos.y += yAddOn;
  479.         }
  480.     }
  481. }
  482.  
  483. // ==========================================================
  484. // Sets left/top border for all TreeNode's drawn on gCanvas
  485. // (int leftBord, int topBord)
  486. // ----------------------------------------------------------
  487. function setLeftAndTopBorderForWholeTree(leftBord, topBord)
  488. {
  489.     var node;   // TreeNode
  490.     for (var i = 0; i < gTreeNodes.length; i++)
  491.     {
  492.         // Get TreeNode from gTreeNodes[]
  493.         node = gTreeNodes[i];
  494.         if (!node.hidden)
  495.         {
  496.             node.pos.x += leftBord;
  497.             node.pos.y += topBord;
  498.         }
  499.     }
  500. }
  501.  
  502. // ===============================================================
  503. // Sets border for all nodes - which determines overall tree size
  504. // (int bordSize)
  505. // ---------------------------------------------------------------
  506. function setBorderForAllNodes(bordSize)
  507. {
  508.     var node;   // TreeNode
  509.     for (var i = 0; i < gTreeNodes.length; i++)
  510.     {
  511.         // Get TreeNode from gTreeNodes[] and set its border
  512.         node = gTreeNodes[i];
  513.         node.border = bordSize;
  514.     }
  515. }
  516.  
  517. // ============================================================
  518. // Returns width and height of the whole tree as a Point(x,y)
  519. // ------------------------------------------------------------
  520. function treeDimensions()
  521. {
  522.     // TreeNode and 6 integers
  523.     var node;
  524.     var minX = 0;
  525.     var maxX = 0;
  526.     var minY = 0;
  527.     var maxY = 0;
  528.     var tWid = 0;
  529.     var tHgt = 0;
  530.     
  531.     // -----------------------------------------
  532.     for (var i = 0; i < gTreeNodes.length; i++)
  533.     {
  534.         // Get TreeNode from gTreeNodes[]
  535.         node = gTreeNodes[i];
  536.         if (!node.hidden)
  537.         {
  538.             // Set max/min XY for whole tree
  539.             if (node.pos.x + node.width > maxX)
  540.                 maxX = node.pos.x + node.width;
  541.  
  542.             if (node.pos.x < minX)
  543.                 minX = node.pos.x;
  544.  
  545.             if (node.pos.y + node.height > maxY)
  546.                 maxY = node.pos.y + node.height;
  547.  
  548.             if (node.pos.y < minY)
  549.                 minY = node.pos.y;
  550.         }
  551.     }
  552.  
  553.     // Set tree width and height
  554.     tWid = Math.ceil(maxX - minX);
  555.     tHgt = Math.ceil(maxY - minY);
  556.     
  557.     // Return width and height as a Point(x,y)
  558.     return new Point(tWid, tHgt);
  559. }
  560.  
  561. // ===============================================================
  562. // Sets node.hidden for all nodes in sub-tree below passed root 
  563. // Returns the number of nodes in the sub-tree below passed root
  564. // (TreeNode root, boolean hide)
  565. // ---------------------------------------------------------------
  566. function markSubTreeAsHiddenOrVisible(root, hide)
  567. {
  568.     // Initialize tree size global variable
  569.     gSubTreeSize = 0;
  570.  
  571.     // Run recursive procedure that increments global var
  572.     walkSubTree(root, hide);
  573.  
  574.     // Recursion complete - So return tree size
  575.     return gSubTreeSize;
  576. }
  577.  
  578. // ============================================================
  579. // RECURSIVE routine to visit all TreeNode's below passed root 
  580. // (TreeNode t, boolean hide)
  581. // ------------------------------------------------------------
  582. function walkSubTree(t, hide)
  583. {
  584.     var c, s;  // TreeNodes
  585.     
  586.     // --------------------------------------
  587.     // Mark TreeNode as hidden or visible
  588.     t.hidden = hide;
  589.  
  590.     // Add to count of num TreeNode's in sub-tree 
  591.     if (t.hiddenTreeSize > 0)
  592.         gSubTreeSize += t.hiddenTreeSize;
  593.     else
  594.         gSubTreeSize ++;
  595.  
  596.     // --------------------------------------
  597.     // Move to next TreeNode in sub-tree
  598.     c = t.child;
  599.     if(c !== null)
  600.     {
  601.         // ***********************************
  602.         // *******   RECURSIVE CALL   ********
  603.         // ***********************************
  604.         walkSubTree(c, hide);
  605.         s = c.sibling;
  606.         
  607.         while(s != null)
  608.         {
  609.             // ***********************************
  610.             // *******   RECURSIVE CALL   ********
  611.             // ***********************************
  612.             walkSubTree(s, hide);
  613.             s = s.sibling;
  614.         }
  615.     }
  616. }
  617.